public class SudokuProblem {
    private final int r = 9;
    private long count = 0;
    private final int[][] collInfo = {
            {0, 0},{0, 3},{0, 6},
            {3, 0},{3, 3},{3, 6},
            {6, 0},{6, 3},{6, 6}
    };
    //解
    void sudokuPro(SudokuItem[][] s) {
        int y = 0, x = 0;
        boolean needBack = false;
        while (y < r && y >= 0) {
            while (x < r && x >= 0) {
                //当前的格子是题目格子时
                if (!s[y][x].isCanChange()) {
                    count++;
                    //如果需要回溯，则x--
                    //否则x++跳过
                    if (needBack) {
                        x--;
                        continue;
                    }
                    x++;
                    continue;
                }
                int num = findNum(s,x,y);
                //若没有找到能插入的数，则标记needBack为true，表示应该进行回溯
                needBack = (num == 0);
                if (needBack) {
                    s[y][x].setNum(0);
                    //回溯时清空历史记录，一定要清空，否则会导致回溯后无法再次填写
                    s[y][x].clearHistroy();
                    //进行回溯
                    x--;
                    //printAnswer(s);
                    count++;
                    continue;
                }

                //插入数字
                s[y][x].setNum(num);
                //插入历史记录
                s[y][x].addHistory(num);
                //printAnswer(s);
                x++;
                count++;
            }
            if (needBack) {
                y--;
                x = 8;
            } else {
                y++;
                x = 0;
            }
        }
        printAnswer(s);
    }
    private int findNum(SudokuItem[][] s,int x, int y) {
        //待填的数1-9
        for (int i = 1; i <= r; i++) {
            count++;
            if (s[y][x].inHistory(i)) continue;
            boolean findSuccess = true;
            //判断横向有是否有相同的
            for (int j = 0; j < r; j++) {
                count++;
                if (j == x) continue;
                if (i == s[y][j].getNum()) {
                    findSuccess = false;
                    break;
                }
            }
            if (!findSuccess)continue;
            //判断纵向是否有相同的
            for (int j = 0; j < r; j++) {
                count++;
                if (j == y) continue;
                if (i == s[j][x].getNum()) {
                    findSuccess = false;
                    break;
                }
            }
            if (!findSuccess)continue;
            int sY = collInfo[s[y][x].getCollect()][0];
            int sX = collInfo[s[y][x].getCollect()][1];
            //判断小宫格内是否有相同的
            for (int j = sY; j < sY + 3; j++) {
                for (int k = sX; k < sX + 3; k++) {
                    count++;
                    if (j == y && k == x) continue;
                    if (i == s[j][k].getNum()) {
                        findSuccess = false;
                        break;
                    }
                }
            }
            if (!findSuccess)continue;

            //能到达这里说明待填的数没有冲突，返回该数
            return i;
        }
        //如果for循环结束还是没有结果，则返回0代表没有找到无冲突的数
        return 0;
    }
    void printAnswer(SudokuItem[][] s) {
        System.out.println("解题完成，共运算"+count+"次");
        System.out.println("===============================");
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < r; j++) {
                System.out.print(s[i][j].getNum()+" ");
            }
            System.out.println();
        }
    }
    //通过坐标判断当前格子是属于哪个宫格
    private int findCollect(int x, int y) {
        if(x < 3){
            if(y < 3) return 0;
            else if(y < 6) return 3;
            else return 6;
        }else if (x < 6){
            if(y < 3) return 1;
            else if(y < 6) return 4;
            else return 7;
        }else{
            if(y < 3) return 2;
            else if(y < 6) return 5;
            else return 8;
        }
    }
    //通过int数组构建SudokuItem数组
    SudokuItem[][] initSudokuItem(int[][] numbers) {
        SudokuItem[][] s = new SudokuItem[9][9];
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < r; j++) {
                s[i][j]  = new SudokuItem(numbers[i][j], (numbers[i][j] == 0), findCollect(j, i));
            }
        }
        return s;
    }
}
